class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        int count=0;
        quickSort(arr, 0, arr.size()-1);
        return arr;
        // write code here
    }
    
    
    
    void quickSort(vector<int>& arr,int left, int right)
    {
        int count;
        int index=partition(arr, left,  right, count);
        if(left<index-1)
        {
          //  partition(arr,left,index-1,count);
            quickSort(arr,left,index-1);
        }
        if(index+1<right)
        {
          //  partition(arr,index+1,right,count);
            quickSort(arr,index+1,right);
        }   
    }
    
   int partition(vector<int> &arr,int left,int right,int & count)
    {
 
        if(count>9999000)
        {
          //  return;
        }
        
        int temp=arr[left];
        while(left<right)
        {
            while(left<right && arr[right]>=temp)
                right--;
            if(left<right)
            {
                arr[left]=arr[right];
              //  left++;
            }
            while(left<right && arr[left]<=temp)  // 这里一定要<=  只是小于是不行的   如果没有等于号，那么在某次partition的时候，如果left指针和right指针所指的数字是相等的，还有temp是相同的,就会陷入死循环
                left++;
            if(left<right)
            {
                arr[right]=arr[left];
               // right--;
            }
            
        }
        arr[left]=temp;
   //     if(0<(left-1))
   //     {
   //     partition(arr,  0, left-1,count);
   //     }
   //     if((left+1) < (arr.size()-1)  )
   //     {
   //     partition(arr,  left+1, arr.size()-1,count);
   //     }
        
    return left;
    }
   
    
    
};





////这种方式的递归调用 层数太多  显示超运行时间的   但是思路应该是对的  要减少递归调用就用一个新的函数返回 index，然后再调用递归函数 


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        int count=0;
        partition(arr, 0, arr.size()-1);
        return arr;
        // write code here
    }
    
    
int partition(vector<int> &arr, int left, int right)
{
	int realleft = left;
	int temp = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= temp)
			right--;
		if (left < right)
		{
			arr[left] = arr[right];
			//  left++;
		}
		while (left < right && arr[left] <= temp)  // 这里一定要<=  只是小于是不行的
			left++;
		if (left < right)
		{
			arr[right] = arr[left];
		}
	}
	arr[left] = temp;
	if (realleft < (left - 1))
	{
		partition(arr, realleft, left - 1);
	}
	if ((left + 1) < (arr.size() - 1))
	{
		partition(arr, left + 1, arr.size() - 1);
	}

	return left;
}

};